Recently, as a technique resulting from combination of techniques in various fields, such as image processing, electronic control, polymer materials, and optics, a Rapid Prototyping System called 3-dimentional printer technique has been widely used. The rapid prototyping system is a system for manufacturing a physical model by laminating rapid solidification materials such as phenolic resin with uniform thickness. The system is advantageous in that time for developing new products can be reduced, that it is possible to model products in complicate and geometrical shapes, and that a designer can directly assemble or interpret an actual model.
A 3-dimensional (3D) mesh model is applied at CAD modeling of such rapid prototyping system, and is represented by a group of surrounding polygonal faces, and includes a list of three tables, i.e., a vertex table represented by rectangular coordinate values of a point, an edge table represented by coordinate values of vertices or their indices, and a polygonal face table represented by edges or indices of vertices. A file format widely used for a 3D mesh model is STL (Stereo Lithography). The STL file format can be obtained by converting external file formats such as PLY (Polygon File Format or Standard Triangle Format), DAE (Collada File Format), OBJ (Alias Wavefront Object), and OFF (Object File Format). Unlike PLY, DAE, OBJ and OFF files, the STL file format includes normal vector information for indicating the direction of a face in consideration of a rapid prototyping system, in addition to information represented by the list of three tables.
Meanwhile, considering the characteristics of the rapid prototyping industry where various fields are combined, the need for integrity guarantee and authentication of a 3D mesh model that is given and taken as a final product of joint corporation has been continuously increased. In the actual manufacturing process, in order to reduce errors of data and increase precision, software for identifying, verifying and modifying manufactured 3D data have been used. As techniques widely used to satisfy the need for integrity guarantee and authentication of data, there are a cryptographic technique and a watermarking technique. However, considering the characteristics of the rapid prototyping industry, a process of applying a 3D mesh model to meet the use of a trial product after demodulating is required, and thus the use of cryptographic technique is extremely limited.
In contrast, the watermarking technique for preventing illegal copying and protecting a copyright of a copyright holder by embedding user information (watermark) into data to hide from a user can solve the problem of the cryptographic technique because the technique directly embeds information into a model. Thus, the watermarking technique can be used for authenticating integrity of a 3D mesh model. It is possible for the watermarking technique to embed a watermark into a 3D mesh model by using information such as the coordinate values of a vertex, the length of an edge, the area or likelihood of a polygon, the ratio of an area, the color of an area or a vertex, and the normal vector of a vertex.
Hereinafter, researches for watermarking of a 3D mesh model that have been variously developed along with the image and video fields will be explained.
First, Ohbuchi proposed TSQ and TVR algorithms, together with the concept of three-dimensional model watermarking (R. Ohbuchi, H. Masuda, and M. Aono, “Watermarking Three Dimensional Polygonal Models,” Proceedings of the ACM Multimedia 97′, Seattle, Wash., U.S.A. November 1997, pp. 261-272). TSQ algorithm is an algorithm for embedding a watermark using the ratio of the lengths of two sides of a triangle and the ratio between the height of a triangle and its base, wherein the watermark is embedded by modifying and changing the positions of vertices so as to have particular ratios. TVR algorithm is an algorithm using the ratio of the volume of a tetrahedron to express a watermark by modifying the ratio of the volume of the tetrahedron by changing the coordinates of a particular vertex.
In a similar way, Chang et al. embedded a watermark by changing the ratio of the length of an edge with four triangles as the basic factor (Chang min Chou, and Din Chang Tseng. “Technologies for 3D Model Watermarking: A Survey,” International Journal of Computer Science and Network Security, Vol. 7 No. 2 Feb. 2007).
Benedens proposed two watermarking algorithms, i.e., VFA and TFA, where large-capacity information can be embedded (O. Benedens “Two High Capacity Methods for Embedding Public Watermarks into 3D Polygonal Models” Proceedings of the Multimedia and Security-Worshop at ACM Multimedia 99, Orlando. Fla., 1999. pp. 95˜99). In VFA algorithm, a watermark is embedded by designating one triangle, and then dividing vertices into several groups according to their distances to the mass center of the designated triangle, and modifying the coordinates of the vertices within the groups. In TFA algorithm, a watermark is embedded by designating one triangle, finding all triangles that share an edge with the designated triangle, sorting the distances from the vertices that does not share the edge to an edge of the shared triangle according to the distances, and modifying the value of the height of each triangle.
Benedens also proposed an algorithm for embedding a watermark using a normal vector (O. Benedens, “Watermarking of 3D Polygon Based Models with Robustness against Mesh Simplification.” Proceedings of SPIE: Security and Watermarking of Multimedia Contents, 1999. Vol. 3657, pp. 329˜340), and this is an algorithm that requires an original work, wherein a watermark is embedded by changing the distribution of the normal vector of a triangle mesh.
In addition, there is an algorithm proposed by Toub (S. Toub, A. Healy, “Efficient Mesh Licensing,” Computer Science 276r, Harvard University, May 2001). In this algorithm, two models A and B are obtained by moving vertices of an original model into an opposite direction under the condition where phase information is not changed, then in case of embedding bit-information 1 based on watermark information to be embedded, coordinate values of model A were used, and in case of embedding bit-information 0, coordinate values of model B were used. The Toub's algorithm maintains constant robustness against attacks by movement, rotation, scaling, cropping, and re-sorting of vertices, but is disadvantageous in that in the process of extracting a watermark, the algorithm requires information on the models A and B that were used for embedding and an original model.
Praun et al. introduced a watermark algorithm relatively robust against typical attacks (E. Praun, H. Hoppe and A. Finkelstein, “Robust Mesh Watermarking,” SIGGRAPH Proceeding, 1999, pp. 69˜76). Praun's algorithm made a scalar-based function by inputting the coordinates of vertices of a mesh model, and set the strength of embedding by using it to change the coordinates of the vertices.
However, lots of conventional researches on watermarking algorithms of a 3D model have been performed based on a method of embedding noise which cannot be visually verified, and they show that after a watermark is embedded, precision of an original model is substantially decreased and the shape of the model itself is deformed. And, almost all of the researches have focused on robustness of a watermark, and researches on preservation of precision of a model itself have been insignificant. This means that in the rapid prototyping system or aerospace model manufacturing field that require high precision, conventional algorithms cannot be used. To be specific, the rapid prototyping system, for example, refers to a system for manufacturing a trial product by cutting materials using a cutting tool such as laser or knife and laminating the materials. The main feature of the rapid prototyping system lies in maintaining high precision; however, according to conventional watermarking algorithms, there is no error or improper factor in design, and a watermark itself would be an improper factor in the rapid prototyping system.
Accordingly, the above-mentioned conventional algorithms can be used for protecting copyrights in the animation, simulation and game fields, but since the conventional watermarking algorithms lead to distort a 3-dimentional shape, thereby decreasing precision, in an applicable field such as rapid prototyping that requires high precision, the shape of a trial product is distorted, and thus these algorithms cannot be used in manufacturing places.